package bin_tree.leetcode;

import java.util.HashMap;
import java.util.Map;

/**
 * 判断平衡树
 */
public class Num110 {
    // 使用Map存储每个出现节点的高度
    Map<TreeNode,Integer> map = new HashMap<>();
    public boolean isBalanced(TreeNode root) {
        // 1.空树
        if(root == null) {
            return true;
        }
        // 2.求当前的左右子树高度
        int leftHeight = 0;
        int rightHeight = 0;
        if (map.containsKey(root.left)) {
            // root.left节点的高度已经算过了
            leftHeight = map.get(root.left);
        }else {
            // 通过递归函数计算该节点的高度并存入map中
            leftHeight = height(root.left);
            map.put(root.left,leftHeight);
        }
        if (map.containsKey(root.right)) {
            // root.left节点的高度已经算过了
            rightHeight = map.get(root.right);
        }else {
            // 通过递归函数计算该节点的高度并存入map中
            rightHeight = height(root.right);
            map.put(root.right,rightHeight);
        }
        int heightAbs = Math.abs(leftHeight - rightHeight);
        if (heightAbs > 1) {
            return false;
        }
        // 递归去看左树和右树是否同时是平衡树
        return isBalanced(root.left) && isBalanced(root.right);
    }
    // 求树的高度问题
    public int height(TreeNode root) {
        if (root == null) return 0;
        return 1 + Math.max(height(root.left),height(root.right));
    }
}
